package org.laizili.solution.leetcode;

import org.laizili.structure.tree.bitree.TreeNode;

/**
 * <a href="https://leetcode.cn/problems/sum-of-root-to-leaf-binary-numbers/">1022. 从根到叶的二进制数之和</a>
 * <p>
 * tags: 二叉树遍历应用;
 */
public class Problem1022 {

    private static class Solution {
        public int sumRootToLeaf(TreeNode root) {
            return traverse(root, 0);
        }

        private int traverse(TreeNode root, int sum) {
            if (root == null) {
                return 0;
            }
            sum = (sum << 1) | root.val;
            if (root.left == null && root.right == null)
                return sum;
            int leftSum = 0, rightSum = 0;
            if (root.left != null) {
                leftSum = traverse(root.left, sum);
            }
            if (root.right != null) {
                rightSum = traverse(root.right, sum);
            }
            return leftSum + rightSum;
        }
    }
}
